package com.hy.three400;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:删除星号以后字典序最小的字符串
 * <p>
 * 给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。
 * 当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
 * 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
 * 请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
 * User:Mr.Du
 * Date:2024/6/2
 * Time:21:12
 */
public class ClearStars {
    /**
     * 清除字符串s中的星号("*")，使得每个星号都被其左侧最近的非星号字符替代。
     * 如果星号左侧没有非星号字符，则忽略该星号。
     *
     * @param s 输入的字符串，可能包含星号字符。
     * @return 返回清除星号后的字符串。
     */
    public String clearStars(String s) {
        // 标记数组，用于记录每个位置的字符是否应该被删除
        boolean[] delete = new boolean[s.length()];
        // 创建26个列表，用于存储每个字母对应的非星号字符位置
        List<Integer>[] st = new List[26];
        // 初始化每个列表
        for (int i = 0; i < 26; i++) {
            st[i] = new ArrayList<>();
        }

        // 遍历字符串，处理每个字符
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 如果当前字符不是星号，则将其位置加入到对应的列表中
            if (c != '*') {
                st[c - 'a'].add(i);
                continue;
            }
            // 如果当前字符是星号，则标记为删除，并尝试删除列表中最右侧的非星号字符位置
            delete[i] = true;
            for (List<Integer> p : st) {
                if (!p.isEmpty()) {
                    delete[p.remove(p.size() - 1)] = true;
                    break;
                }
            }
        }

        // 构建结果字符串
        StringBuilder ans = new StringBuilder();
        // 遍历原字符串，忽略被标记为删除的字符
        for (int i = 0; i < s.length(); i++) {
            if (!delete[i]) {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }


    public static void main(String[] args) {
        String s = "k*dy*";
        ClearStars clearStars = new ClearStars();
        String s1 = clearStars.clearStars(s);
        System.out.println(s1);
    }
}
